# 根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 
# 
#  给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞
#  （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律： 
# 
#  
#  如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 
#  如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 
#  如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 
#  如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 
#  
# 
#  下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态
# ，返回下一个状态。 
# 
#  给定当前 board 的状态，更新 board 到下一个状态。 
# 
#  注意 你不需要返回任何东西。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
# 输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
#  
# 
#  示例 2： 
#  
#  
# 输入：board = [[1,1],[1,0]]
# 输出：[[1,1],[1,1]]
#  
# 
#  
# 
#  提示： 
# 
#  
#  m == board.length 
#  n == board[i].length 
#  1 <= m, n <= 25 
#  board[i][j] 为 0 或 1 
#  
# 
#  
# 
#  进阶： 
# 
#  
#  你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。 
#  本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？ 
#  
# 
#  Related Topics 数组 矩阵 模拟 👍 652 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        shift = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        # m行n列
        m = len(board)
        n = len(board[0])
        # copyarr = [[x for x in row] for row in board]
        # for i in range(m):
        #     for j in range(n):
        #         # 每次循环后刷新one的数量重新开始计数
        #         one = 0
        #         # 计算周围8个（如果周围没有细胞则不计算）活细胞数量
        #         for x, y in shift:
        #             if 0 <= i + x < m and 0 <= j + y < n:
        #                 if copyarr[i + x][j + y] == 1:
        #                     one += 1
        #         # 得到了周围活细胞的数目，即可书写判断逻辑了
        #         if copyarr[i][j] == 1:
        #             if one < 2 or one > 3:
        #                 board[i][j] = 0
        #             elif one == 2 or one == 3:
        #                 board[i][j] = 1
        #         else:
        #             if one==3:
        #                 board[i][j]=1
        # # print(board)
        """
        方法二:原地转换
        思路:细胞只有1和0两种状态,现在加两个符合状态,令由死到活的细胞为2 令由活细胞到死细胞的为-1
        """
        for i in range(m):
            for j in range(n):
                # 每次循环后刷新one的数量重新开始计数
                one = 0
                # 计算周围8个（如果周围没有细胞则不计算）活细胞数量
                for x, y in shift:
                    if 0 <= i + x < m and 0 <= j + y < n:
                        if board[i + x][j + y] == 1 or board[i + x][j + y] == -1:
                            one += 1
                # 得到了周围活细胞的数目，即可书写判断逻辑了
                if board[i][j] == 1:
                    if one < 2 or one > 3:
                        board[i][j] = -1
                    elif one == 2 or one == 3:
                        board[i][j] = 1
                else:
                    if one == 3:
                        board[i][j] = 2
        # 再遍历一次把-1 和 2 替换为 0 和 1
        for i in range(m):
            for j in range(n):
                if board[i][j] == -1:
                    board[i][j] = 0
                elif board[i][j] == 2:
                    board[i][j] = 1

        # print(board)


# leetcode submit region end(Prohibit modification and deletion)
Solution().gameOfLife(board=[[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]])
